home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / c / jpl_c.zip / SORTH.C < prev    next >
Text File  |  1986-05-18  |  2KB  |  75 lines
  1. /* 1.0  11-12-84
  2.  ************************************************************************
  3.  *            Robert C. Tausworthe                *
  4.  *            Jet Propulsion Laboratory            *
  5.  *            Pasadena, CA 91009        1984        *
  6.  ************************************************************************
  7.  *    Heapsort subroutine, using an iterative form of the usual
  8.  *    recursive algorithm, such as found in
  9.  *
  10.  *    Aho, A. V., Hopcroft, J. E., and Ullmann, J. D., THE DESIGN AND
  11.  *    ANALYSIS OF ALGORITHMS, Addison-Wesley Pub. Co., pp. 87-92.
  12.  *
  13.  *    The function is written so the array type is unknown to the
  14.  *    algorithm, but is known to comp() and exch().  The comparison
  15.  *    function comp(i, j) must be positive if, and only if, the array
  16.  *    elements indexed by i and j are out of sort.  The function
  17.  *    exch(i, j) must exchange the elements at indices i and j.
  18.  */
  19.  
  20. #include "defs.h"
  21. #include "stdtyp.h"
  22.  
  23. int     (*gcomp)();    /* global compare and exchange functions */
  24. VOID     (*gexch)();
  25.  
  26. /************************************************************************/
  27.     VOID
  28. sortH(n, comp, exch)    /* Heapsort array of 0..(n-1) items compared
  29.                by comp(i,j), exchanged by exch(i,j)     */
  30. /*----------------------------------------------------------------------*/
  31. unsigned n;
  32. int (*comp)();
  33. VOID (*exch)();
  34. {
  35.     unsigned i;
  36.     int j;
  37.  
  38.     gcomp = comp;        /* set functions global to this subroutine */
  39.     gexch = exch;
  40.  
  41.     for (j = n-- / 2 - 1; j >= 0; j--)    /* build heap. n is now      */
  42.         heap(j, n);        /* the index of the last element. */
  43.     for (i = n; i > 0; )
  44.     {    (*gexch)(0, i--);
  45.         heap(0, i);
  46.     }
  47. }
  48.  
  49. /*\p*********************************************************************/
  50.     LOCAL VOID
  51. heap(dad, rightmost)    /* build heap from (dad-1)-st to (rightmost-1)-st
  52.                elements of the array.            */
  53. /*----------------------------------------------------------------------*/
  54. unsigned dad, rightmost;
  55. {            /* Array to sort in heapsort algorithm is 1..n, */
  56.             /* but arrays in C go 0..(n-1). Thus the offset.*/
  57.  
  58.     unsigned son, r;
  59.  
  60.     FOREVER
  61.     {    if ((son = 2 * dad + 1) > rightmost) /* if no sons remain, */
  62.             return;
  63.         if (son < rightmost)    /* if both right and left sons    */
  64.             if ((*gcomp)(r = son + 1, son) > 0)
  65.                 son = r;
  66.         /* son is now the index of the maximum son-element of dad */
  67.         if ((*gcomp)(son, dad) > 0)
  68.         {    (*gexch)(son, dad);
  69.             dad = son;
  70.         }
  71.         else
  72.             return;
  73.     }
  74. }
  75.